User blog:Fejfo/Function levels
This is inspired by https://googology.wikia.org/wiki/User_blog:Jacquesbailhache/Simmons_Ordinal_Notation . I had this idea more than a year ago but couldn't get it to work (or at least not very strong). But seeing an "example" made it much easier to extend it (even though I had to add several new defintions) I think \( f_n f_0 \) should approximately correspond to Δn in Simmons ordinal notation. And thus assuming his analysis is correct \( h(\omega) \) is the BHO. Defintion Range of symbols *\( \alpha, \beta, \gamma\in \rm{Ord}, \gamma < \alpha \) *\( \lambda \) is any limit ordinal *\( n,m \in \mathbb N\) *\( F_\alpha = \) class of all total functions of level \( \alpha \) *\( f_\alpha \) the standard function of level \( \alpha \) *\( g_\alpha \) any function of level \( \alpha \) *\( G_\alpha \subset F_\alpha \) *\( \beta_0, \beta_1, \cdots, \beta_n = 1 \) any series of decreasing ordinals. *\( \omega \) the smallest limit ordinal *\( g \) any function of a level greater than 0 *\( x \) any argument in the domain of \( g \) Level *\( F_0 = \rm{Ord}\) *\( F_\alpha = \{ f : F_\gamma \mapsto F_\gamma : \gamma < \alpha \}\) for \( \alpha \) non-zero. *\( g \) is of level \( \alpha \) if \( \min \{ \beta : g \in F_\beta \} = \alpha \) A lambda calculus like notation is used for function application. Ie: \( f \beta_0 \beta_1 \cdots \beta_n = f(\beta_0)(\beta_1)\cdots(\beta_n) \). Supermums of higher levels *\( \sup G_0 = \bigcup G_0 \), the usual defintion of supremum for ordinals. *\( \alpha \) non-zero:\( \sup (G_\alpha) g_\gamma = \sup \{ g g_\gamma : g \in G_\alpha \}\) Transfinite iteration *\( g^0 x = x \) *\( g^{\alpha+1} x = g (g^\alpha x) \) *\( g^\alpha x = \sup \{ g^{\gamma} x : \gamma < \alpha \} \) for limit \( \alpha \) Standard functions *\( \rm{Fix}~f \alpha = f^\omega (\alpha+1)\), \( \rm{Fix}~f \) is the function taking an ordinal \( \alpha \) to the first fixedpoint of \( f \) past \( \alpha \) *\( \rm{Next~}f \alpha = \min \{ f(\beta)> \alpha : \beta \in \rm{Ord} \} \), slightly weakens a function to a function which doesn't get stuck. *\( f_0 = 0\) *\( f_1 \alpha = \rm{Next}~(\alpha \mapsto \omega^\alpha) \) *\( f_{\beta_0+1} g_{\beta_0} g_{\beta_1} \cdots g_{\beta_n} = \rm{Fix}~( \alpha \mapsto g_{\beta_0}^\alpha g_{\beta_1} \cdots g_{\beta_n} 0 ) \) Where \( \beta_0 \ge 1 , \beta_n= 1 \) *(Polymorphism) \( g_{ \beta_0+1} g_{\beta_1} = g_{ \beta_0+1 } f_{\beta_0} g_{\beta_1} \) *\( f_{\alpha} g_{\gamma} = \sup \{ f_\delta g_\gamma : \gamma < \delta < \alpha \} \) for limit \( \alpha \). In a simmilar way we could continue defining a level \( \Omega \) function. Fundamental sequences I assign a fundamental sequence to any fully simplyfied expression \( e \) representing a limit ordinal. (Note assigning fundamental sequences to ordinals would require and additional definition of standard expressions) *\( \omegan = n\) *Standard fundamental sequences for \( + , \cdot, \wedge \) *\( (g^\alpha x)n = g^{\alphan} x \) for limit \( \alpha \) *\( (f_{\alpha} g_{\gamma} = \sup \{ f_\delta g_\gamma : \gamma < \delta < \alpha \} )n = f_{\alphan+m} g_\gamma \) where \( m = \min \{ m \in \mathbb N : \alpham > \gamma \}\), for limit \( \alpha \) Now we can end in style by defining a large number. Fast growing hierachy on these expressions *\( h_0 = f_1 \) *\( h_{e+n+1} m = h_{e+n}^m m \) *\( h_e n = h_{en} n\) *\( h_\alpha n = h_e n \) where \( e \) is \( \alpha \) fully simplified Final results *function on ordinals \( h \alpha = f_{\alpha} f_0 \) for \( \alpha > 0\) *supremum of ordinals expressible with standard functions: \( \rm{Fix~}h 0 = h^\omega(1) \) *number : \( h_{h^\omega(1) + 1 }(3) \) Analysis Up to the LVO I steal a beautiful way to precisly match the veblen function using transfinite iteration from SON. The problem with using normal functions \( f \) is that \( f^\alpha(0) = f^\omega (0) \forall \alpha > \omega \). But if you transition to the function \( g= Fix f \), naming the next fixed points of \( f \) you can define \( g^\alpha 0 = \) the \( \alpha\)th fixed point of \( f \). Ie, the next function in the Veblen hierachy. After retransitioning to \( Fix ( \alpha \mapsto g^\alpha 0 ) \) the scheme can be repeated. For analysis it will thus be useful to define \( \varphi'(\cdots) = Next ( \alpha \mapsto \varphi(\cdots, \alpha) )\). An other useful fact is the for a set \( F \) of normal functions \( \sup \{ \rm{Fix~}f : f\in F \}\) is the function taking an ordinal \( \alpha \) to the first common fixed point of all of \( F \) past \( \alpha \). So it doesn't get stuck on \( \varphi_\omega \) either. ( \( \beta @\alpha \) represents \( \beta \) followed by \( \alpha \) zero's. Failed analysation attempt using the following \( \theta \) OCF: \(C_0(\alpha,\beta) = \beta \cup\{ 0 \} \\ C_{n+1}(\alpha,\beta) = \{ \gamma + \delta, \Omega_\gamma, \theta_\eta(\gamma) : \gamma, \delta, \eta \in C_n(\alpha,\beta), \eta< \alpha \} \\ C(\alpha,\beta) = \bigcup_{n\in\omega} C_n(\alpha,\beta) \\ \theta_\alpha = \rm{Enum~}\{ \beta \not \in C(\alpha,\beta) \} \\ \theta'_\alpha = \rm{Next~} \theta_\alpha \) This is hard to analyze, the problem is that I don't know a comparable notation with higher level functions and thus can't find expressions for what \( f_4 \) is. Functions for analysis Idea *We know how to describe ordinals. *We defined \( \theta'_\alpha \) to describe level 1 functions. We say \( \rm{lvl}_1(\alpha) = \theta'_\alpha \) *We can describe the effect of level 2 functions on level 1 functions, by the effect it has on the subscript of \( \theta'_\alpha \), eg \( f_2 \theta'_\alpha = \theta'_{\alpha+1}\) We say, \( \rm{lvl}_2(1) = f_2 \) and more general \( \rm{lvl}_2 \alpha (\rm{lvl}_1 \beta) = \rm{lvl}_1(\beta+\alpha) \) *We can describe the effect of level 3 functions on level 2 functions in a similar way: \( f_3 \rm{lvl}_2(\alpha) = \rm{lvl}_2(\alpha\cdot\Omega) \), descrbied by the effect on \( \alpha \). \( \rm{lvl}_3 \beta \rm{lvl}_2 \alpha= \rm{lvl}_2 {\alpha \cdot \beta }\) *\( \rm{lvl}_4 \beta \rm{lvl}_3 \alpha = \rm{lvl}_3(\alpha^\beta \) Second attempt to the BHO This doesn't correspond to the result from Simmons ordinal notation, even though I can't find my mistake I don't seem to understand my own extension. Category:Blog posts